﻿\subsection{Суффиксный массив и массив LCP}
\label{subsection:bigexp-sufarr}

Для быстрой проверки того, является ли слово $w$ минимальным
запрещённым словом в некотором $\beta$-свободном языке первого
уровня, мы будем использовать \textit{суффиксный массив} этого слова.
Назовём $i$-м суффиксом слова $w$ суффикс $w[i..|w|]$. Пустой
суффикс по определению будем считать $(|w|{+}1)$-м суффиксом $w$.
Суффиксный массив $suff_w$~--- это перестановка индексов $\{1,\ldots,|w|{+}1\}$,
которая задаёт порядок суффиксов в порядке лексикографической сортировки.
Кроме того, мы будем использовать \textit{массив LCP}, в котором
хранится длина {\it наибольшего общего префикса} ($lcp$) для каждой соседней в порядке
сортировки пары суффиксов. Массив $lcp_w$ имеет длину $|w|$, и
в элементе $lcp_w[i]$ хранится длина $lcp$ суффиксов
с номерами $suff_w[i]$ и $suff_w[i{+}1]$. Например, для строки $cababa$
суффиксный массив равен $[7,6,4,2,5,3,1]$, а массив $lcp$~---
$[0,1,3,0,2,0]$.

Существуют быстрые алгоритмы построения суффиксного массива и массива $lcp$
произвольного слова за линейное время (\cite{Manber,Karkkainen,Schurmann}). Однако,
для уменьшения константного множителя, мы рассмотрим алгоритм,
который за линейное время строит суффиксный массив и массив
$lcp$ для некоторого слова $wc$, используя известные $suff_w$ и $lcp_w$.
Для построения алгоритма нам понадобятся две леммы.

\begin{lmm} \label{sufarr}
Пусть $c \in \Sigma$, $w \in \Sigma^*$, $x, y, z$~--- суффиксы $w$, $x < y < z$, $xc < yc$.
Тогда $xc < zc$.
\end{lmm}

\begin{proof}
Пусть $xc$~--- не префикс $yc$. Выберем такой индекс $i$, что $xc[j]=yc[j]$ при $j<i$,
$xc[i]<yc[i]$. Тогда либо существует такое $h<i$, что $xc[h]=yc[h]<zc[h]$ и $xc[j]=zc[j]$ при $j<h$,
либо $|y|<|z|$ и $xc[i]<yc[i]\le zc[i]$. В обоих случаях $xc < zc$.

Пусть теперь $xc$~--- префикс $yc$. Тогда либо существует такое $h\le|xc|$, что $xc[h]=yc[h]<zc[h]$
и $xc[j]=zc[j]$ при $j<h$, либо $|zc|>|xc|$ и $xc$~--- префикс $zc$. Вновь в обоих случаях $xc < zc$.
\end{proof}

\begin{lmm} \label{lcptrans}
Пусть $lcp(u,v)$~--- длина наибольшего общего префикса слов $u$ и $v$. Тогда если $u \le v \le w$,
то $lcp(u,w) = \min(lcp(u,v), lcp(v,w))$.
\end{lmm}
\begin{proof}
Если некоторое слово $w\in\Sigma^*$ имеет длину $n$, то будем считать, что фиктивный символ
$w[n+1]$ меньше всех символов из $\Sigma$. Пусть, без ограничения
общности, $lcp(u,v) \le lcp(v,w)$. Случай $u=v$ очевиден. Пусть $u<v$. Тогда для всех
от 1 до $lcp(u,v)$ выполняется $u[i]=v[i]=w[i]$. Кроме того,
$u[lcp(u,v){+}1] < v[lcp(u,v){+}1] \le w[lcp(u,v){+}1]$, откуда $lcp(u,v)=lcp(v,w)$.
\end{proof}

Теперь рассмотрим алгоритм, который по слову $wc$ и массивам $suff_w$ и $lcp_w$ строит
массивы $suff_{wc}$ и $lcp_{wc}$. Нам понадобится стек $S$, в котором мы будем хранить пары чисел
$(suff, lcp)$~--- номер суффикса и длину $lcp$ этого суффикса с предыдущим суффиксом в стеке
(если он есть).
\texttt{\begin{tabbing}
01. $suff_{wc}[1] \leftarrow |wc| + 1$\\
02. $lcp_{wc}[1] \leftarrow 0$\\
03. $p \leftarrow 2$\\
04. $S \leftarrow (suff_w[1], 0)$\\
05. для \= всех $i \in [2, |w|{+}1]$\\
06. \> $x \leftarrow suff_w[i]$\\
07. \> $clcp \leftarrow lcp_w[i{-}1]$\\
08. \> если \= $lcp$ $suff_w[i{-}1]$-го и $suff_w[i]$-го суффикса $wc$ длиннее $clcp$\\
09. \>\> $clcp \leftarrow clcp + 1$\\
10. \> пока \= $S \neq \emptyset$ и $x$-й cуффикс $wc$ больше $S.top.suff$\\
11. \>\> $clcp \leftarrow \min(clcp, S.top.lcp)$\\
12. \>\> $suff_{wc}[p] \leftarrow S.top.suff$\\
13. \>\> $lcp_{wc}[p] \leftarrow S.top.lcp$\\
14. \>\> $p \leftarrow p + 1$\\
15. \>\> извлечь $S.top$ из стека\\
16. \> $S \leftarrow (x, clcp)$\\
17. \> если \= цикл в строках 10-15 ни разу не выполнился\\
18. \>\> $lcp_{wc}[p] \leftarrow \min(lcp_{wc}[p], clcp)$\\
19. пока \= $S \neq \emptyset$ \\
20. \> $suff_{wc}[p] \leftarrow S.top.suff$\\
21. \> $lcp_{wc}[p] \leftarrow S.top.lcp$\\
22. \> $p \leftarrow p + 1$\\
23. \> извлечь $S.top$ из стека\\
\end{tabbing}}
Рассмотрим этот алгоритм подробнее. В цикле в строках 5-18 мы рассматриваем $i$-й
в лексикографическом порядке суффикс $w$, который начинается с позиции $x$. Далее
следует обработка $x$-го суффикса $wc$. Мы сперва удаляем из
стека $S$ все суффиксы, меньшие $x$-го суффикса $wc$, а потом добавляем $x$-й суффикс $wc$ в стек.
Значит, суффиксы $wc$ в стеке $S$ расположены по убыванию. Покажем, что массив $suff_{wc}$ строится
корректно. Рассмотрим $u$-й суффикс слова $wc$ и все суффиксы, которые будут
расположены в $suff_{wc}$ правее его. Достаточно показать, что все эти суффиксы будут больше $u$-го. 
Если $u$-й суффикс записывается в $suff_{wc}$ в строке 12, то обрабатываемый $x$-й суффикс больше
$u$-го как в слове $w$, так и в слове $wc$. Все суффиксы после $x$-го в массиве $suff_w$
будут добавлены в массив $suff_{wc}$ позже $u$-го суффикса, но они больше его по
лемме~\ref{sufarr}. Кроме того, позже $u$-го суффикса в массив будут добавлены суффиксы,
лежащие ниже его в стеке $S$, которые также больше его.

Теперь рассмотрим построение массива $lcp_{wc}$. Во время цикла в строках 5-18 значение $clcp$
равно длине $lcp$ обрабатываемого $x$-го суффикса и суффикса на вершине $S$. Поскольку в начале
обработки $x$-го суффикса на вершине стека лежит его левый сосед в суффиксном массиве $suff_w$
(см. строки 4 и 16), присвоение в строках 7-9 корректно (строки 8-9 соответствуют случаю, когда
некоторый $i$-й суффикс является префиксом $j$-го суффикса и в слове $w$, и в слове $wc$).
Вместе с каждым суффиксом из стека мы храним длину его $lcp$ с предыдущим суффиксом в стеке.
Значит, после удаления элемента с вершины стека, обновление $clcp$ в строке 11 корректно по
лемме~\ref{lcptrans}. Если последний записанный в $suff_{wc}$ номер суффикса был записан на $p$-е
место, то в $lcp_{wc}[p]$ записывается длина $lcp$ этого суффикса и текущего суффикса на вершине
стека. Если после этой операции хотя бы раз выполнится цикл в строках 10-15,
то вершина стека будет добавлена в массив следующей, и значение $lcp_{wc}[p]$ изменять не нужно.
В противном случае мы должны обновить значение $lcp_{wc}[p]$ (см. строки 17-18) в соответствии
с леммой~\ref{lcptrans}.

Осталось оценить время работы приведённого алгоритма. Каждый суффикс ровно один раз
добавляется в стек и один раз удаляется из него, а значит, суммарное количество
выполнений цикла в строках 10-15 линейно зависит от $|wc|$. Проверку в строке 8 и
сравнение в строке 10 можно выполнить за константное время, используя известную
длину $lcp$ (зная эту длину, можно сразу же сравнить у двух суффиксов первый различный
символ). Все остальные операции, очевидно, также выполняются за константное время.

Итак, мы построили алгоритм, позволяющий за линейное время пересчитать суффиксный
массив слова при дописывании в конец слова одной буквы. В процессе рекурсивного перебора корней
запрещённых слов, описанного в параграфе~\ref{subsection:bigexp-algo}, мы будем 
поддерживать суффиксный массив и массив $lcp$ текущего корня, пересчитывая его за
линейное время при дописывании к корню новой буквы. Кроме того, по построенным
массивам $suff_w$ и $lcp_w$ мы сможем предварительно посчитать за линейное время для
всех суффиксов слова $w$ длину их $lcp$ с первым суффиксом (самим словом $w$).
